package q70_climbStairs;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        System.out.println(s.climbStairs(45));
    }

    public int climbStairs(int n) {
        // 很容易就可以知道这样的推断过程
//        if (n == 1 || n == 0){
//            return 1;
//        }
//        return climbStairs(n - 1) + climbStairs(n - 2);


        // 但我们还是希望直接在方程内解决
        int[] f = new int[n + 1];
        f[0] = f[1] =  1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];



    }


}
